Query Processing and Optimization

查询处理共分为三个过程：执行 (Parsing & Translation)、优化 (Optimization)、估计 (Evaluation)

Parsing & Translation

Measures of Query Cost

$t_{T}$ : time to transfer one block
$t_{S}$ : time for one seek
Cost for b block transfers plus S seeks: $b * t_{T} + S * t_{S}$

Selection

Linear Search(equality on key): 线性搜索
- worst cost: $b_{r} * t_{T} + t_{S}$ (关系表存放在 $b_{r}$ 个 block 中)
- average cost: $(b_{r} / 2) * t_{T} + t_{S}$ (在查询值为主码的情况下)
Primary B+-Tree index(equality on key): B+ 树主索引搜索
- Cost: $(h_{i} + 1) * (t_{T} + t_{S})$ ， $h_{i}$ 是 B+ 树的高度，每次需要从 Disk 中 Seek 该块并读入，而后面的 1 是指最后找到目标块时，需要进行 seek+transfer(使用 Index 必不可少的)
Primary B+-Tree index(equality on nonkey): B+ 树主索引，单值 (非唯一)
- Cost: $h_{i} * (t_{T} + t_{S}) + t_{S} + b * t_{T}$ ，其中 b 是包含查找值的数据块个数。
Secondary B+-Tree index(equality on key): B+ 树辅助索引
- Cost: $(h_{i} + 1) * (t_{T} + t_{S})$ ，和 B+ 树主索引搜索原理一样
Secondary B+-index on nonkey: B+ 树辅助索引，单值 v(非唯一)
- Cost: $(h_{i} + m + n) * (t_{T} + t_{S})$
- m 指 B+ 树中，对应查找值 v 索引的块的数量
- n 指包含查找值 v 的数据块的数量

External Merge Sort

M: memory size，内存共可存放的页的个数
大致流程可以通过下图表示：
- 第一轮传入 M 块数据，进行原地排序。（使用快排、堆排序等原地排序算法）
- 第二轮及后面每轮，合并 M-1 个有序序列。
- 注意，需要在 memory 块中预留一个区域存放排序好的有序序列，所以每轮合并后，有序序列的段数就少了 M-1 倍（预留出一个输出块的原因是：可以以块为单位写回，节省时间开销）
block transfers
- Total number of merge passes required: $⌈ \log_{M - 1} (b_{r} / M) ⌉$ (第一次排序被视为初始化，不计入其中，可带入检验 $b_{r} = M$ 和 $b_{r} = M - 1$ 的情况)
- 因为在一轮归并排序中，一个块需要经历写入内存、然后写回磁盘，所以每轮的开销是 $2 b_{r}$
- 最后一轮排序，不计算写回 disk 的开销。
- 所以总次数是 $b_{r} (2 ⌈ \log_{M - 1} (b_{r} / M) ⌉ + 1)$
seek times
- 第一次排序： $⌈ b_{r} / M ⌉$ 次 seek
- 第二次排序及后面的排序：假设每次读入/写出的块数为 $⌈ b_{b} ⌉$ 则需要 $⌈ b_{r} / b_{b} ⌉$ 次读出和写入，此处共经历 $⌈ \log_{M - 1} (b_{r} / M) ⌉$ 轮排序，最后一轮不用写入，故一共为 $⌈ b_{r} / b_{b} ⌉ (2 ⌈ \log_{M - 1} (b_{r} / M) ⌉ - 1)$ 次 seek
- 总计为 $2 ⌈ b_{r} / M ⌉ + ⌈ b_{r} / b_{b} ⌉ (2 ⌈ \log_{M - 1} (b_{r} / M) ⌉ - 1)$

Join

(1) Nested-Loop Join
$r ⋈_{θ} s$ ，伪代码如下：

for each tuple tr in r do begin
	for each tuple ts in s do begin
		test pair (tr, ts) to see if they satisfy the join condition
		if they do, add tr·ts to the result
	end
end

最坏情况（只能载入两个 block，r/s 各一个）
- block transfers: $b_{r} + n_{r} * b_{s}$
  - r 共要载入 $b_{r}$ 次，而 s 共要载入 $n_{r} * b_{s}$ 次
- seek times: $b_{r} + n_{r}$
  - r 共要 seek $b_{r}$ 次，而 s 共要 seek $n_{r}$ 次
最好情况（全部元组都能直接载入内存）
- block transfers $b_{r} + b_{s}$
- seek times: $2$

(2) Block Nested-Loop Join

for each block Br in r do begin
	for each block Bs in s do begin
		for each tuple tr in Br do begin
			for each tuple ts in Bs do begin
				test pair (tr, ts) to see if they satisfy the join condition
				if they do, add tr·ts to the result
			end
		end
	end
end

最坏情况（只能载入两个 block，r/s 各一个）
- block transfers: $b_{r} + b_{r} * b_{s}$
  - r 共要载入 $b_{r}$ 次，而 s 共要载入 $b_{r} * b_{s}$ 次
- seek times: $2 b_{r}$
  - r 共要 seek $b_{r}$ 次，而 s 共要 seek $b_{r}$ 次
最好情况（全部元组都能直接载入内存）
- block transfers $b_{r} + b_{s}$
- seek times: $2$

(3) Indexed Nested-Loop Join

原理：外层遍历 tuple(每次读取一个 block)，内层使用索引匹配（如 B+ 树索引等）
最坏情况（只能载入两个 block，r/s 各一个）
因为索引本身的复杂度较复杂，故只给出较粗略的估算 $b_{r} * (t_{T} + t_{S}) + n_{r} * c$
- 其中 $c$ 指单次查询的平均开销

(4) Merge-Join

算法流程
1. 根据 index 的 attributes 进行排序
2. 连接两个排序过的表（从头到尾扫描）
理想情况下（每个块只需要读进内存一次）
- block transfers: $b_{r} + b_{s}$ +(排序)
- seek times: $⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉$ +(排序)

(5) Hash-Join

大致流程如下

将r划分成nh个块
将s划分成nh个块

for 0 to nh-1
	对r对应块中的元素建立索引Ri
	for 遍历s对应块中的元素
		检索索引Ri
		for 所有匹配的tuple in r
			join
		end
	end
end

假设 r,s 分别被划分了 $n_{r}, n_{s}$ 个块，但当 $n_{r}, n_{s} > M$ 超过内存的容纳空间时，则需要进行递归划分。

若没有递归划分
- block transfer: $3 (b_{r} + b_{s}) + 4 n_{h}$
  - 划分过程需要遍历表，包含读出和写回 $2 * (b_{r} + b_{s})$
  - 匹配过程需要遍历表，只包含读出 $b_{r} + b_{s}$
  - 但是若 Hash 表非满，则至多制造出 $n_{h}$ 个非满块，涉及划分的写回和匹配的读出，作用于两个表，故共 $4 n_{h}$ (实际中 $n_{h}$ 一般很小，可以忽略不计)
- seek times: $2 (⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉) + 2 n_{h}$
  - 划分过程需要遍历表，假设每次放入内存块中 $b_{b}$ 个，则读出写回共需 $2 (⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉)$ 次
  - 匹配过程中直接取 Hash 块，共 $2 n_{h}$
若有递归划分
- 递归划分的原则是，每次将划分的大小降为原来的 $M - 1$ ，直至每个划分的最多占 $M$ 块为止（使得内存能够容纳下，以便于建立索引）
- block transfer: $2 (b_{r} + b_{s}) ⌈ l o g_{M - 1} (b_{s}) - 1 ⌉ + b_{r} + b_{s}$
  - 共进行 $⌈ l o g_{M - 1} (b_{s}) - 1 ⌉$ 轮
  - 其余参照没有递归划分的情况
- seek times: $2 (⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉) ⌈ l o g_{M - 1} (b_{s}) - 1 ⌉ + 2 n_{h}$
  - 共进行 $⌈ l o g_{M - 1} (b_{s}) - 1 ⌉$ 轮
  - 其余参照没有递归划分的情况

Evaluation

对一些单操作的复杂度有了解之后，可以使用物化 (Materialization) 和流水 (pipelining) 的方法将他们串起来

实体化：依次进行表达式的计算，构建前缀树递归进行
流水线：同时评估多个操作

Optimization

Equivalence Rule(等价关系表达式)

Conjunctive selection operations can be deconstructed into a sequence of indicidual selections $σ_{θ_{1} \land θ_{2}} (E) = σ_{θ_{1}} (σ_{θ_{2}} (E))$
Selection operations are commutative $σ_{θ_{1}} (σ_{θ_{2}} (E)) = σ_{θ_{2}} (σ_{θ_{1}} (E))$
Only the last in a sequence of projection operations is needed, the others can be ommitted. $Π_{L_{1}} (Π_{L_{2}} (. . . (Π_{L_{n}} (E)) . . .)) = Π_{L_{1}} (E)$
Selections can be combined with Cartesian products and theta joins.
(1) $σ_{θ} (E_{1} \times E_{2}) = E_{1} ⋈_{θ} E_{2}$
(2) $σ_{θ_{1}} (E_{1} ⋈_{θ_{2}} E_{2}) = E_{1} ⋈_{θ_{1} \land θ_{2}} E_{2}$
Theta-join operations (and natural joins) are commutative. $E_{1} ⋈_{θ} E_{2} = E_{2} ⋈_{θ} E_{1}$
Natural join operatins are associative $(E_{1} ⋈ E_{2}) ⋈ E_{3} = E_{1} ⋈ (E_{2} ⋈ E_{3})$ , Theta joins are associative in the following manner $(E_{1} ⋈_{θ_{1}} E_{2}) ⋈_{θ_{2} \land θ_{3}} E_{3} = E_{1} ⋈_{θ_{1} \land θ_{3}} (E_{2} ⋈_{θ_{2}} E_{3})$ , where $t h e t a_{2}$ involves attributes from only $E_{2}$ and $E_{3}$ .
The selection operation distributes over the theta join operation under the following two conditions:
(1) When all the attributes in $θ_{0}$ involve only the attributes of one of the expressions ( $E_{1}$ ) being joined $σ_{θ_{0}} (E_{1} ⋈_{θ} E_{2}) = (σ_{θ_{0}} (E_{1})) ⋈_{θ} E_{2}$
(2) When $θ_{1}$ involves only the attributes of $E_{1}$ and $θ_{2}$ involves only the attributes of $E_{2}$ . $σ_{θ_{1} \land θ_{2}} (E_{1} ⋈_{θ} E_{2}) = (σ_{θ_{1}} (E_{1})) ⋈_{θ} (σ_{θ_{2}} (E_{2}))$
The projetion operation distributes over the theta join operation as follows:
(1) if $θ$ involves only attributes from $L_{1} \cup L 2$ : $Π_{L 1 \cup L_{2}} (E_{1} ⋈_{θ} E_{2}) = (Π_{L_{1}} (E_{1})) ⋈_{θ} (Π_{L_{2}} (E_{2}))$
(2) Consider a join $E_{1} ⋈_{θ} E_{2}$ .
(3) Let $L_{1}$ and $L_{2}$ be sets of attributes from $E_{1}$ and $E_{2}$ respectively
(4) Let $L_{3}$ be attributes of $E_{1}$ that are involved in join condition $θ$ , but are not in $L_{1} \cup L_{2}$
(5) Let $L_{4}$ be attributes of $E_{2}$ that are involved in join condition $θ$ , but are not in $L_{1} \cup L_{2}$
$Π_{L_{1} \cup L_{2}} (E_{1} ⋈_{θ} E_{2}) = Π_{L_{1} \cup L_{2}} ((Π_{L_{1} \cup L_{3}} (E_{1})) ⋈_{θ} (Π_{L 2 \cup L_{4}} (E_{2})))$
The set operations union and intersection are commutative $E_{1} \cup E_{2} = E_{2} \cup E_{1}$ , $E_{1} \cap E_{2} = E_{2} \cap E_{1}$
Set union and intersection are assocative $(E_{1} \cup E_{2}) \cup E_{3} = E_{1} \cup (E_{2} \cup E_{3})$ , $(E_{1} \cap E_{2}) \cap E_{3} = E_{1} \cap (E_{2} \cap E_{3})$
The selection operation distributes over $\cap$ , $\cup$ and $-$ $σ_{θ} (E_{1} - E_{2}) = σ_{θ} (E_{1}) - σ_{θ} (E_{2})$
The projection operation distributes over union $Π_{L} (E_{1} \cup E_{2}) = (Π_{L} (E_{1})) \cup (Π_{L} (E_{2}))$

Cost Estimation(结果集大小估计)

基本概念
- $n_{r}$ : number of tuples in a relation $r$
- $b_{r}$ : number of blocks containing tuples of $r$
- $l_{r}$ : size of a tuple of $r$
- $f_{r}$ : blocking factor of $r$
- $V (A, r)$ : number of distinct values that appear in $r$ for attribute $A$ ; same as the size of $Π_{A} (r)$
- $b_{r} = ⌈ \frac{n_{r}}{f_{r}} ⌉$
算法估计
- 选择估计 $σ_{A = v} (r)$
  - 一般假设为均匀分布
  - $n_{r} / V (A, r)$
- 复杂选择估计
  - 合取 $σ_{θ_{1} \land θ_{2} \land \dots \land θ_{n} (r)}$ : $n_{r} \cdot \frac{s_{1} \cdot s_{2} \dots s_{n}}{n_{r}^{n}}$
  - 析取 $σ_{θ_{1} \lor θ_{2} \lor \dots \lor θ_{n} (r)}$ : $n_{r} \cdot (1 - (1 - \frac{s_{1}}{n_{r}}) (1 - \frac{s_{2}}{n_{r}}) \dots (1 - \frac{s_{n}}{n_{r}}))$
- 连接估计 $r ⋈ s$
  - 若两个关系无共同属性: $n_{r} \cdot n_{s}$
  - 若共同属性是 r 的 key: $s i z e \leq n_{s}$
  - 若共同属性是 s 到 r 的 foregin key: $n_{s}$
  - 若共同属性不是 key: $min (\frac{n_{s} \cdot n_{r}}{V (A, s)}, \frac{n_{s} \cdot n_{r}}{V (A, r)})$
- 投影: $Π (s)$ : $V (A, r)$
- 聚合: $G (s)$ : $V (A, r)$
- 集合：转换为合取和析取
Heuristic Optimization 探索式的优化
- 尽早进行 selection
- 尽早进行 projection
- 选择最严格的 selection 和 operations 操作